#include "Solution.hpp"
#include "Tournee.hpp"
#include <cassert>
#include <cstdlib>
#include <algorithm>

bool 	operator==(const SolutionEval& in1, const SolutionEval& in2)
{
	return (in1.seNTournees == in2.seNTournees)	&& (in1.seDistance == in2.seDistance);
    //return (in1.seDistance == in2.seDistance);
}

bool 	operator<=(const SolutionEval& in1, const SolutionEval& in2)
{
	if (in1.seNTournees == in2.seNTournees)
	{
		return (in1.seDistance <= in2.seDistance);
	}
	
	return (in1.seNTournees <= in2.seNTournees);
}


bool	operator<(const SolutionEval& in1, const SolutionEval& in2)
{
	if (in1.seNTournees == in2.seNTournees)
	{
		return (in1.seDistance < in2.seDistance);
	}
    	
	return (in1.seNTournees < in2.seNTournees);
}

/*
bool	operator<(const SolutionEval& in1, const SolutionEval& in2)
{
	if ((in1.seAdvantage + in1.seWait) == (in2.seAdvantage + in2.seWait))
	{
		return (in1.seNTournees < in2.seNTournees);
	}
	
	return ((in1.seAdvantage + in1.seWait) < (in2.seAdvantage + in2.seWait));
}
*/

std::string     SolutionEval::toString() const
{
    char buffer[0x1000];
    
    sprintf(buffer, "(%u, T : %.2f, D : %.2f, W : %.2f, A : %.2f)", seNTournees, seTime, seDistance, seWait, seAdvantage);
    return (std::string(buffer));
}

Solution::Solution(VRPTW&   inVRPTW)
    :   soVRPTW(inVRPTW),
        soTournees(inVRPTW.size(), Tournee(inVRPTW, 0)),
        soTourneesTmp(inVRPTW.size(), Tournee(inVRPTW, 0)),
        soStates(inVRPTW.size()),
        soTourneeByClient(inVRPTW.size())
{
    std::pair<unsigned, unsigned>   p;
    
    for (unsigned i = 0 ; i < soVRPTW.size() ; i++)
    {
        // @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
        // attention raw memcpy ABI dependant
        // @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
        
        soTournees[i].toId = i;
        soTourneesTmp[i].toId = i;
        //memcpy(&soTournees[i], &i, sizeof(unsigned));
        //memcpy(&soTourneesTmp[i], &i, sizeof(unsigned));
        p.first = p.second = i;
        // tous les clients a servir
        soClientsToServe.insert(p);
        soTourneeByClient[i] = 0xFFFFFFFF;
    }
}

Solution::Solution(const Solution& inSolution)
    :   soVRPTW(inSolution.soVRPTW),
        soTournees(inSolution.soVRPTW.size(), Tournee(inSolution.soVRPTW, 0)),
        soTourneesTmp(inSolution.soVRPTW.size(), Tournee(inSolution.soVRPTW, 0)),
        soStates(inSolution.soVRPTW.size()),
        soTourneeByClient(inSolution.soVRPTW.size())
{
    std::pair<unsigned, unsigned>   p;
    
    for (unsigned i = 0 ; i < soVRPTW.size() ; i++)
    {
        // @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
        // attention raw memcpy ABI dependant
        // @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
        
        memcpy(&soTournees[i], &i, sizeof(unsigned));
        memcpy(&soTourneesTmp[i], &i, sizeof(unsigned));
        p.first = p.second = i;
        // tous les clients a servir
        soClientsToServe.insert(p);
        soTourneeByClient[i] = 0xFFFFFFFF;
    }
    
    this->operator=(inSolution);
}

Solution::~Solution()
{}


unsigned		Solution::getTourneeByClient(unsigned inClient) EXC_THROWER()
{
	EXC_RETHROW_BEGIN()
	{
		if (soTourneeByClient[inClient] == 0xFFFFFFFF)
			EXC_THROW("client not in solution");
			
		return (soTourneeByClient[inClient]);
	}
	EXC_RETHROW_END()
}

Tournee&	Solution::operator[](unsigned inIndex) EXC_THROWER()
{
    if (inIndex >= soTournees.size())
    {
		std::cerr << " >> " << inIndex << std::endl;
        EXC_THROW("wrong index given for tournee WR access");
    }
    if (soStates[inIndex] == Solution::TOURNEE_UNKNOWN)
    {
        std::cerr << ">> tournee index : " << inIndex << std::endl;
        EXC_THROW("!!! trying to modify tournee which is unknown, please valid or restore before modification");
    }
    if (soTournees.size() == 0)
        EXC_THROW("unable to access, solution is empty");
    
    // acces en ecriture
    soStates[inIndex] = Solution::TOURNEE_UNKNOWN;
    return (soTournees[inIndex % soTournees.size()]);
}


void			Solution::clear()
{
	std::pair<unsigned, unsigned>   p;
	
	soClientsToServe.clear();
	soTourneeByClient.clear();
	
    for (unsigned i = 0 ; i < soVRPTW.size() ; i++)
    {
        soTournees[i].clear();
		soTourneesTmp[i].clear();
		soStates[i] = TOURNEE_VALID;
        p.first = p.second = i;
        // tous les clients a servir
        
        soClientsToServe.insert(p);
        soTourneeByClient.push_back(0xFFFFFFFF);
    }
	
}

//// NONONONONON !!!!
// on degage ce systeme d'historique moisi
// on laisse validate/restore
// et on ajoutera une grosse methode Solution::check(), qui pour chaque tournee
// va recuperer la liste des clients et verifier que tout est ok (pas de doublons, etc)
// et fera en gros l'"eval" de la solution, chaque tournee est sensee etre valide
// le seul truc c'est qu'on peut avoir des doublons de clients ou il peut en manquer !

void        Solution::validateTournee(unsigned inIndex) EXC_THROWER()
{
    std::list<Operation>::const_iterator     it;
    
    if (inIndex >= soTournees.size())
        EXC_THROW("wrong index given for tournee validation");
    
    // recuperer les informations depuis la tournee
    // pour mettre a jour les infos globales de la solution
    Tournee&    t = soTournees[inIndex];


    for (it = t.getHistory().begin() ; it != t.getHistory().end() ; ++it)
    {
        const Operation&    op = *it;
        
        if (soVRPTW.isRDepot(op.opClient))
			continue;
        
        switch(op.opType)
        {
            case Operation::INSERT:
                if (soTourneeByClient[op.opClient] == 0xFFFFFFFF)
                {
                    soTourneeByClient[op.opClient] = inIndex;
                    soClientsToServe.erase(soClientsToServe.find(op.opClient));
                }
                else if (soTourneeByClient[op.opClient] != inIndex)
                {
                    if (soTournees[soTourneeByClient[op.opClient]].exist(op.opClient))
                    {
                        if (soStates[soTourneeByClient[op.opClient]] == Solution::TOURNEE_VALID)
                        {
                            std::cerr << "while inserting client " << op.opClient << " inside tournee " << inIndex << std::endl; 
                            EXC_THROW("corruption of the solution, by client insertion");
                        }
                        else
                        {
                            std::cerr << "you've validated a tournee which contains a client already inside another tournee (which is in edition mode at this time), make sure to check integrity of data, then do a global validation of every tournee" << std::endl;
                            soClientsToServe.erase(soClientsToServe.find(op.opClient));
                        }
                    }
                    else
                        soClientsToServe.erase(soClientsToServe.find(op.opClient));
                }
                break;
                
            case Operation::ERASE:
                if (soTourneeByClient[op.opClient] == inIndex)
                {   
                    soTourneeByClient[op.opClient] = 0xFFFFFFFF;
                    soClientsToServe[op.opClient] = op.opClient;
                }
                // else case could be used here to check errors
                break;
            
            case Operation::REPLACE:
                soTourneeByClient[op.opClientReplaced] = inIndex;
                break;
            
            case Operation::UNKNOWN:
                EXC_THROW("while validating tournee, history contains an UNKNOWN operation !");
                break;
        }
    }

    soStates[inIndex] = Solution::TOURNEE_VALID;
    
    soTournees[inIndex].clearHistory();
    
    // probleme operator= due a const unsigned,
    // le code qui suit remplace l'operator=
    soTourneesTmp[inIndex].clear(); 
    soTourneesTmp[inIndex].append(soTournees[inIndex]);
    
    //std::cout << soTournees[inIndex].toString() << std::endl;
    //std::cout << soTourneesTmp[inIndex].toString() << std::endl;
}

void        Solution::restoreTournee(unsigned inIndex) EXC_THROWER()
{
    if (inIndex >= soTournees.size())
        EXC_THROW("wrong index given for tournee restoration");
    
    //std::cout << "OLD" << std::endl;
    //std::cout << soTournees[inIndex].toString() << std::endl;
    
    //std::cout << "RESTORE INTO" << std::endl;
    //std::cout << soTourneesTmp[inIndex].toString() << std::endl;
    
    soTournees[inIndex].clearHistory();
    
    // operator= replace
    soTournees[inIndex].clear();
    soTournees[inIndex].append(soTourneesTmp[inIndex]);

    soStates[inIndex] = Solution::TOURNEE_VALID;
}

std::string     Solution::toString()
{
    std::string res;
           std::deque<Tournee>*    tournees = 0;
    char                buffer[0x1000];
    unsigned    k = 0;
    
    sprintf(buffer, "SOLUTION (%2u) =========================================\n", soClientsToServe.size());
    res += buffer;
    res += isComplete() ? "COMPLETE\n" : "INCOMPLETE\n";
    for (unsigned i = 0 ; i < soTournees.size() ; i++)
    {
        if (soTournees[i].size() == 0)
        {
            k++;
            continue;
        }
        
        tournees = (soStates[i] == Solution::TOURNEE_VALID) ? &soTournees : &soTourneesTmp;
        sprintf(buffer, "%2u %s\n", i, (*tournees)[i].toString().c_str());
        res += buffer;
    }
    
    return (res);
}

bool            Solution::isComplete() const
{   return (soClientsToServe.empty());  }

void            Solution::complete()
{
    std::map<unsigned, unsigned>::iterator it;
    unsigned                slot = 0;
    
    if (isComplete())
		return;
    
    while (soTournees[slot].size() != 0)
        slot++;
    
    do
    {
        this->operator[](slot).insertClient(Tournee::INSERT_BEGIN, soClientsToServe.begin()->second);
        this->validateTournee(slot);
        slot++; 
    }
    while (!soClientsToServe.empty());
}

void			Solution::fillDeque(std::deque<unsigned>& inDeque) const
{
	unsigned 	i = 0;
	
	for (i = 0 ; i < soTournees.size() ; i++)
	{
		if (soTournees[i].size() == 0)
			continue;
			
		soTournees[i].fillDeque(inDeque);
	}
}

unsigned		Solution::getPredecessorOf(unsigned inClient) const EXC_THROWER()
{
	EXC_RETHROW_BEGIN()
	{
		unsigned	t;
		
		if (inClient >= soTourneeByClient.size())
		{
			std::cout << soTourneeByClient.size() << std::endl;
			EXC_THROW("inClient given is bad");
		}
		
		if ((t = soTourneeByClient[inClient]) == 0xFFFFFFFF)
			EXC_THROW("inClient given is not in this solution");
			
		return soTournees[t].getPredecessorOf(inClient);
	}
	EXC_RETHROW_END()
}

void			Solution::swapTournees(unsigned inIndex1, unsigned inIndex2)
{
	Tournee t(soVRPTW, 0);
	
	t.clear();
	t.append(soTournees[inIndex1]);
	soTournees[inIndex1].clear();
	soTournees[inIndex1].append(soTournees[inIndex2]);
	soTournees[inIndex1].clearHistory();
	soStates[inIndex1] = TOURNEE_VALID;
	
	soTournees[inIndex2].clear();
	soTournees[inIndex2].append(t);
	soTournees[inIndex2].clearHistory();
	soStates[inIndex2] = TOURNEE_VALID;
	
	for (unsigned i = 0 ; i < soTourneeByClient.size() ; i++)
	{
		if (soTourneeByClient[i] == inIndex1)
			soTourneeByClient[i] = inIndex2;
		else if (soTourneeByClient[i] == inIndex2)
			soTourneeByClient[i] = inIndex1;
	}
}

void        Solution::buildTourneeByWait(std::multimap<double, unsigned>& inTourneeByWait, double inSensivity)
{
    TourneeEvalResult   evalres;
    
    inTourneeByWait.clear();
    
    for (unsigned i = 0 ; i < soTournees.size() ; i++)
    {
        if (soTournees[i].getNbClients() == 0)
        {
            continue;
        }
        
        soTournees[i].eval(&evalres);
        if (evalres.erTotalWait < inSensivity)
            inTourneeByWait.insert(std::pair<double, unsigned>(evalres.erTotalWait, i));
    }
}

void        Solution::eval(SolutionEval* inEval)
{
    TourneeEvalResult   evalres;
    unsigned k = 0;
    unsigned i = 0;
    
    assert(inEval != 0);
    memset(inEval, 0, sizeof(SolutionEval));
    
    inEval->seTime = 0.;
    inEval->seDistance = 0.;
    inEval->seWait = 0.;
    inEval->seAdvantage = 0.;
    
    for (i = 0 ; i < soTournees.size() ; i++)
    {
        if (soTournees[i].size() == 0)
        {
            k++;
            continue;
        }
        
        soTournees[i].eval(&evalres);
        inEval->seTime +=  evalres.erTotalTime;
        inEval->seDistance += evalres.erTotalDistance;
        inEval->seWait += evalres.erTotalWait;
        inEval->seAdvantage += evalres.erAdvantage;
    }
    
    inEval->seNTournees = (i - k);
}

std::pair<unsigned, unsigned>        Solution::getRandomPair() const
{
    std::pair<unsigned, unsigned>   p;
    
    do
    {
        p.first = rand() % soTournees.size();
    }   while (soTournees[p.first].size() == 0);
    
    do
    {
        p.second = rand() % soTournees.size();
    }   while (soTournees[p.second].size() == 0 || (p.first == p.second));
    
    return (p);
}

void    Solution::buildTourneeBySize(std::multimap<unsigned, unsigned>& inTourneeBySize) const
{
    inTourneeBySize.clear();
    
    for (unsigned i = 0 ; i < soTournees.size() ; i++)
    {
        if (soTournees[i].getNbClients() == 0)
            continue;
            
        inTourneeBySize.insert(std::pair<unsigned, unsigned>(soTournees[i].size(), i));
    }
}

unsigned        Solution::getEmptyRandomTournee() const
{
    unsigned    r;
    
    do
    {
        r = rand() % 100;
        
    }   while (soTournees[r].getNbClients() != 0);
    
    return (r);
}

unsigned        Solution::getFilledRandomTournee() const
{
    unsigned    r;
    
    do
    {
        r = rand() % 100;
        
    }   while (soTournees[r].getNbClients() == 0);
    
    return (r);
}

void            Solution::shift()
{
    for (unsigned i = 1 ; i < 99 ; i++)
    {
        swapTournees(i - 1, i);
    }
    
    swapTournees(0, 99);
}

unsigned        Solution::getFirstFilledFrom(unsigned n) const
{
    unsigned    i = n;
    
    for (; i < 100 ; i++)
    {
        if (soTournees[i].getNbClients() != 0)
            return (i);
    }
    
    return (100);
}

void            Solution::reorganize()
{
    unsigned    n;
    
    for (unsigned i = 0 ; i < 100 ; i++)
    {
        if (soTournees[i].getNbClients() != 0)
            continue;
        else
        {
            n = getFirstFilledFrom(i);
            
            if (n == 100)
                return;
            
            swapTournees(i, n);
        }
    }
}

void			Solution::reorganizeBySizeCouples()
{
	std::multimap<unsigned, unsigned>	tournees_by_size;
	std::multimap<unsigned, unsigned>::iterator	it;
	std::multimap<unsigned, unsigned>::reverse_iterator ir;
	
	this->buildTourneeBySize(tournees_by_size);
	
	it = tournees_by_size.begin();
	ir = tournees_by_size.rbegin();
	
	for (unsigned i = 0 ; i < (tournees_by_size.size() / 2) ; i++, ++it, ++ir)
	{
		if (ir->second == it->second)
			break;
		
		swapTournees(i, ir->second);
		swapTournees(i + 1, it->second);
	}
}

void			Solution::reorganizeByWAFactor()
{
	std::multimap<double, unsigned>		tbf;
	std::multimap<double, unsigned>::iterator	it;
	
	TourneeEvalResult					teval;
	
	for (unsigned i = 0 ; i < soVRPTW.size() ; i++)
	{
		if (soTournees[i].getNbClients() == 0)
			continue;
			
		soTournees[i].eval(&teval);
		tbf.insert(std::pair<double, unsigned>(teval.erAdvantage + teval.erTotalWait, i));
	}
	
	it = tbf.begin();
	for (unsigned i = 0 ; i < tbf.size() ; i++)
	{
		swapTournees(i, it->second);
	}
}

void			Solution::shuffle()
{
	random_shuffle(soTournees.begin(), soTournees.end());
	
	for (unsigned i = 0 ; i < 100 ; i++)
		soTourneesTmp[i] = soTournees[i];
}

void			Solution::printTournee(const std::string& inFilename, unsigned inTournee)
{
	FILE*	file = 0;
	
	if ((file = fopen(inFilename.c_str(), "wt")) == 0)
	{
		perror(inFilename.c_str());
		assert(false);
	}
	
	fprintf(file, "digraph coucou { \nsize=\"20,20\"");
	//soVRPTW.printDotPoints(file);
	
	unsigned client;
	client = DEPOT;
	
	//soVRPTW.printDotPoint(client);
	for (;;)
	{
		soVRPTW.printDotPoint(file, client);
		fprintf(file, "%u -> %u;\n",
			client, soTournees[inTournee].getSuccessorOf(client)
		);
		
		client = soTournees[inTournee].getSuccessorOf(client);
		
		if (client == DEPOT)
			break;
	}
	fprintf(file, "};");
	
	fclose(file);
}

bool			Solution::hasClient(unsigned inClient) const
{
	return (soTourneeByClient[inClient] != 0xFFFFFFFF);
}

